<!DOCTYPE html>
<html lang="zh-cn,en,default">
<head>
  <!-- hexo-inject:begin --><!-- hexo-inject:end --><meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=2">
<meta name="theme-color" content="#222">
<meta name="generator" content="Hexo 4.0.0">
  <link rel="apple-touch-icon" sizes="180x180" href="/images/apple-touch-icon-next.png">
  <link rel="icon" type="image/png" sizes="32x32" href="/images/favicon-32x32-next.png">
  <link rel="icon" type="image/png" sizes="16x16" href="/images/favicon-16x16-next.png">
  <link rel="mask-icon" href="/images/logo.svg" color="#222">

<link rel="stylesheet" href="/css/main.css">


<link rel="stylesheet" href="/lib/font-awesome/css/font-awesome.min.css">


<script id="hexo-configurations">
  var NexT = window.NexT || {};
  var CONFIG = {
    hostname: new URL('http://yoursite.com').hostname,
    root: '/',
    scheme: 'Pisces',
    version: '7.5.0',
    exturl: false,
    sidebar: {"position":"left","display":"post","offset":12,"onmobile":false},
    copycode: {"enable":true,"show_result":true,"style":null},
    back2top: {"enable":true,"sidebar":false,"scrollpercent":false},
    bookmark: {"enable":false,"color":"#222","save":"auto"},
    fancybox: false,
    mediumzoom: false,
    lazyload: false,
    pangu: false,
    algolia: {
      appID: '',
      apiKey: '',
      indexName: '',
      hits: {"per_page":10},
      labels: {"input_placeholder":"Search for Posts","hits_empty":"We didn't find any results for the search: ${query}","hits_stats":"${hits} results found in ${time} ms"}
    },
    localsearch: {"enable":true,"trigger":"auto","top_n_per_article":1,"unescape":false,"preload":false},
    path: 'search.json',
    motion: {"enable":true,"async":false,"transition":{"post_block":"fadeIn","post_header":"slideDownIn","post_body":"slideDownIn","coll_header":"slideLeftIn","sidebar":"slideUpIn"}},
    sidebarPadding: 40
  };
</script>

  <meta name="description" content="站在巨人的肩膀上。">
<meta name="keywords" content="技术, JAVA, 原创">
<meta property="og:type" content="website">
<meta property="og:title" content="子我">
<meta property="og:url" content="http:&#x2F;&#x2F;yoursite.com&#x2F;index.html">
<meta property="og:site_name" content="子我">
<meta property="og:description" content="站在巨人的肩膀上。">
<meta property="og:locale" content="zh-cn">
<meta name="twitter:card" content="summary">

<link rel="canonical" href="http://yoursite.com/">


<script id="page-configurations">
  // https://hexo.io/docs/variables.html
  CONFIG.page = {
    sidebar: "",
    isHome: true,
    isPost: false,
    isPage: false,
    isArchive: false
  };
</script>

  <title>子我</title>
  






  <noscript>
  <style>
  .use-motion .brand,
  .use-motion .menu-item,
  .sidebar-inner,
  .use-motion .post-block,
  .use-motion .pagination,
  .use-motion .comments,
  .use-motion .post-header,
  .use-motion .post-body,
  .use-motion .collection-header { opacity: initial; }

  .use-motion .site-title,
  .use-motion .site-subtitle {
    opacity: initial;
    top: initial;
  }

  .use-motion .logo-line-before i { left: initial; }
  .use-motion .logo-line-after i { right: initial; }
  </style>
</noscript><!-- hexo-inject:begin --><link rel='stylesheet' href='https://cdn.jsdelivr.net/npm/katex@0.10.0/dist/katex.min.css'><!-- hexo-inject:end -->

</head>

<body itemscope itemtype="http://schema.org/WebPage">
  <!-- hexo-inject:begin --><!-- hexo-inject:end --><div class="container use-motion">
    <div class="headband"></div>

    <header class="header" itemscope itemtype="http://schema.org/WPHeader">
      <div class="header-inner"><div class="site-brand-container">
  <div class="site-meta">

    <div>
      <a href="/" class="brand" rel="start">
        <span class="logo-line-before"><i></i></span>
        <span class="site-title">子我</span>
        <span class="logo-line-after"><i></i></span>
      </a>
    </div>
        <p class="site-subtitle">子我的原创IT技术博客</p>
  </div>

  <div class="site-nav-toggle">
    <div class="toggle" aria-label="Toggle navigation bar">
      <span class="toggle-line toggle-line-first"></span>
      <span class="toggle-line toggle-line-middle"></span>
      <span class="toggle-line toggle-line-last"></span>
    </div>
  </div>
</div>


<nav class="site-nav">
  
  <ul id="menu" class="menu">
        <li class="menu-item menu-item-home">

    <a href="/" rel="section"><i class="fa fa-fw fa-home"></i>Home</a>

  </li>
        <li class="menu-item menu-item-tags">

    <a href="/tags/" rel="section"><i class="fa fa-fw fa-tags"></i>Tags</a>

  </li>
        <li class="menu-item menu-item-categories">

    <a href="/categories/" rel="section"><i class="fa fa-fw fa-th"></i>Categories</a>

  </li>
        <li class="menu-item menu-item-archives">

    <a href="/archives/" rel="section"><i class="fa fa-fw fa-archive"></i>Archives</a>

  </li>
      <li class="menu-item menu-item-search">
        <a role="button" class="popup-trigger"><i class="fa fa-search fa-fw"></i>Search
        </a>
      </li>
  </ul>

</nav>
  <div class="site-search">
    <div class="popup search-popup">
    <div class="search-header">
  <span class="search-icon">
    <i class="fa fa-search"></i>
  </span>
  <div class="search-input-container">
    <input autocomplete="off" autocorrect="off" autocapitalize="none"
           placeholder="Searching..." spellcheck="false"
           type="text" id="search-input">
  </div>
  <span class="popup-btn-close">
    <i class="fa fa-times-circle"></i>
  </span>
</div>
<div id="search-result"></div>

</div>
<div class="search-pop-overlay"></div>

  </div>
</div>
    </header>

    
  <div class="back-to-top">
    <i class="fa fa-arrow-up"></i>
    <span>0%</span>
  </div>

  <a href="https://github.com/cyrilney" class="github-corner" title="Follow me on GitHub" aria-label="Follow me on GitHub" rel="noopener" target="_blank"><svg width="80" height="80" viewBox="0 0 250 250" aria-hidden="true"><path d="M0,0 L115,115 L130,115 L142,142 L250,250 L250,0 Z"></path><path d="M128.3,109.0 C113.8,99.7 119.0,89.6 119.0,89.6 C122.0,82.7 120.5,78.6 120.5,78.6 C119.2,72.0 123.4,76.3 123.4,76.3 C127.3,80.9 125.5,87.3 125.5,87.3 C122.9,97.6 130.6,101.9 134.4,103.2" fill="currentColor" style="transform-origin: 130px 106px;" class="octo-arm"></path><path d="M115.0,115.0 C114.9,115.1 118.7,116.5 119.8,115.4 L133.7,101.6 C136.9,99.2 139.9,98.4 142.2,98.6 C133.8,88.0 127.5,74.4 143.8,58.0 C148.5,53.4 154.0,51.2 159.7,51.0 C160.3,49.4 163.2,43.6 171.4,40.1 C171.4,40.1 176.1,42.5 178.8,56.2 C183.1,58.6 187.2,61.8 190.9,65.4 C194.5,69.0 197.7,73.2 200.1,77.6 C213.8,80.2 216.3,84.9 216.3,84.9 C212.7,93.1 206.9,96.0 205.4,96.6 C205.1,102.4 203.0,107.8 198.3,112.5 C181.9,128.9 168.3,122.5 157.7,114.1 C157.9,116.9 156.7,120.9 152.7,124.9 L141.0,136.5 C139.8,137.7 141.6,141.9 141.8,141.8 Z" fill="currentColor" class="octo-body"></path></svg></a>


    <main class="main">
      <div class="main-inner">
        <div class="content-wrap">
          

          <div class="content">
            

  <div class="posts-expand">
        
  
  
  <article itemscope itemtype="http://schema.org/Article" class="post-block home" lang="zh-cn">
    <link itemprop="mainEntityOfPage" href="http://yoursite.com/2020/04/28/Leetcode-number-of-occurrences-of-numbers-in-the-array/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="image" content="https://blog-bucket-1300756499.cos.ap-chengdu.myqcloud.com/avatar.jpg">
      <meta itemprop="name" content="Cyril Nee">
      <meta itemprop="description" content="站在巨人的肩膀上。">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="子我">
    </span>
      <header class="post-header">
        <h1 class="post-title" itemprop="name headline">
          
            <a href="/2020/04/28/Leetcode-number-of-occurrences-of-numbers-in-the-array/" class="post-title-link" itemprop="url">Leetcode number-of-occurrences-of-numbers-in-the-array.</a>
        </h1>

        <div class="post-meta">
            <span class="post-meta-item">
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              <span class="post-meta-item-text">Posted on</span>
              

              <time title="Created: 2020-04-28 15:31:11 / Modified: 15:59:54" itemprop="dateCreated datePublished" datetime="2020-04-28T15:31:11+08:00">2020-04-28</time>
            </span>

          
  
  <span class="post-meta-item">
    
      <span class="post-meta-item-icon">
        <i class="fa fa-comment-o"></i>
      </span>
      <span class="post-meta-item-text">Valine: </span>
    
    <a title="valine" href="/2020/04/28/Leetcode-number-of-occurrences-of-numbers-in-the-array/#comments" itemprop="discussionUrl">
      <span class="post-comments-count valine-comment-count" data-xid="/2020/04/28/Leetcode-number-of-occurrences-of-numbers-in-the-array/" itemprop="commentCount"></span>
    </a>
  </span>
  
  

        </div>
      </header>

    
    
    
    <div class="post-body" itemprop="articleBody">

      
          <h3 id="描述"><a class="markdownIt-Anchor" href="#描述"></a> 描述</h3>
<p>4月28日每日一题。<br />
一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。</p>
<pre><code>示例 1：

输入：nums = [4,1,4,6]
输出：[1,6] 或 [6,1]
</code></pre>
<h3 id="思路"><a class="markdownIt-Anchor" href="#思路"></a> 思路</h3>
<p>面对这个问题的时候，我们可以先简单化这个问题来学习关键解法。<br />
一个整型数组 nums 里除<strong>一</strong>个数字之外，其他数字都出现了两次。要如何找出这个数字呢？<br />
我们可以将整个数组里面的元素进行一次按位异或（xor）的处理。原理是这样的：两个相同数字的异或结果为0，数组中重复的元素异或过程中会被自己消去。</p>
<p>解决了简单版的问题后。我们进行如下思考：如果进行异或之后只能得到两个数字的异或结果，有什么意义呢？进一步思考按位异或的定义（逐个比较二进制位。若不同该位结果为1，相同返回0），即对于为1的某一个二进制位而言，这两个数字该位置在该位一定是不同的。其他重复的元素在该二进制位一定是相同的（要么为0要么为1而且必定成对出现）。 可以由此将数组分成两个单一数字出现一次，其他数字出现两次的子数组。分别进行异或即可。</p>
<p>比如 [4,1,4,6] 二进制分别为[0b100, 0b1, 0b100, 0b110] 总体异或结果为5(Ob111)<br />
任取一位置1，将数组分为<br />
[1],和[4,4,6]<br />
分别异或得到结果[1,6]</p>
<h3 id="复杂度-on"><a class="markdownIt-Anchor" href="#复杂度-on"></a> 复杂度: O(n)</h3>
<h3 id="answers-code"><a class="markdownIt-Anchor" href="#answers-code"></a> Answers Code</h3>
<pre><code>class Solution:
    def singleNumbers(self, nums: List[int]) -&gt; List[int]:
        xorNum = 0
        for num in nums:
            xorNum ^= num
        lowerbit = xorNum &amp; (-xorNum)
        ans = [0,0]
        for num in nums:
            if num &amp; lowerbit:
                ans[0] ^= num
            else:
                ans[1] ^= num
        return ans
</code></pre>

      
    </div>

    
    
    
      <footer class="post-footer">
        <div class="post-eof"></div>
      </footer>
  </article>
  
  
  

        
  
  
  <article itemscope itemtype="http://schema.org/Article" class="post-block home" lang="zh-cn">
    <link itemprop="mainEntityOfPage" href="http://yoursite.com/2020/04/27/Leetcode-No-33-search-in-rotated-sorted-array/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="image" content="https://blog-bucket-1300756499.cos.ap-chengdu.myqcloud.com/avatar.jpg">
      <meta itemprop="name" content="Cyril Nee">
      <meta itemprop="description" content="站在巨人的肩膀上。">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="子我">
    </span>
      <header class="post-header">
        <h1 class="post-title" itemprop="name headline">
          
            <a href="/2020/04/27/Leetcode-No-33-search-in-rotated-sorted-array/" class="post-title-link" itemprop="url">Leetcode No.33 search-in-rotated-sorted-array</a>
        </h1>

        <div class="post-meta">
            <span class="post-meta-item">
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              <span class="post-meta-item-text">Posted on</span>
              

              <time title="Created: 2020-04-27 23:09:56 / Modified: 23:17:25" itemprop="dateCreated datePublished" datetime="2020-04-27T23:09:56+08:00">2020-04-27</time>
            </span>

          
  
  <span class="post-meta-item">
    
      <span class="post-meta-item-icon">
        <i class="fa fa-comment-o"></i>
      </span>
      <span class="post-meta-item-text">Valine: </span>
    
    <a title="valine" href="/2020/04/27/Leetcode-No-33-search-in-rotated-sorted-array/#comments" itemprop="discussionUrl">
      <span class="post-comments-count valine-comment-count" data-xid="/2020/04/27/Leetcode-No-33-search-in-rotated-sorted-array/" itemprop="commentCount"></span>
    </a>
  </span>
  
  

        </div>
      </header>

    
    
    
    <div class="post-body" itemprop="articleBody">

      
          <h3 id="描述"><a class="markdownIt-Anchor" href="#描述"></a> 描述</h3>
<p>4月27日每日一题。</p>
<p>假设按照升序排序的数组在预先未知的某个点上进行了旋转。<br />
( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。<br />
搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。<br />
你可以假设数组中不存在重复的元素。<br />
你的算法时间复杂度必须是 O(log n) 级别。</p>
<h3 id="思路"><a class="markdownIt-Anchor" href="#思路"></a> 思路</h3>
<p>二分查找问题，其实本质上是一样的。 列表是进行过偏移的有序数组。可以先找到有序数组的偏移量。<br />
（比如 [4,5,6,7,0,1,2]，偏移下标为4，即最小元素index为4）。二分时候实际的边界值为（left:(0+4)%7=4, right:(6+4)%7=3）<br />
然后二分即可。</p>
<h3 id="复杂度-ologn"><a class="markdownIt-Anchor" href="#复杂度-ologn"></a> 复杂度: O(log(n))</h3>
<h3 id="answers-code"><a class="markdownIt-Anchor" href="#answers-code"></a> Answers Code</h3>
<pre><code>class Solution:
    def search(self, nums: List[int], target: int) -&gt; int:
        if not nums:
            return -1

        startIndex = self.searchStart(nums, 0, len(nums) - 1)
        return self.dfs(nums, 0, len(nums)-1, target, startIndex)

    # 二分搜索
    def dfs(self, nums, left, right, target, startIndex):
        if left &gt; right:
            return -1
        trueLeft = (left + startIndex) % len(nums)
        trueRight = (right + startIndex) % len(nums)
        if left == right:
            if nums[trueLeft] == target:
                return trueLeft
            return -1
        mid = int((left + right)/2)
        trueMid = (mid + startIndex) % len(nums)
        if nums[trueMid] &gt;= target:
            return self.dfs(nums, left, mid, target, startIndex)
        else:
            return self.dfs(nums, mid+1, right, target, startIndex)

    # 开始下标查询
    def searchStart(self, nums, left, right):
        if left == right:
            return left
        if nums[left] &lt; nums[right]:
            return left
        mid = int((left + right) / 2)
        if nums[mid] &lt; nums[left]:
            return self.searchStart(nums, left, mid)
        return self.searchStart(nums, mid+1, right)
</code></pre>

      
    </div>

    
    
    
      <footer class="post-footer">
        <div class="post-eof"></div>
      </footer>
  </article>
  
  
  

        
  
  
  <article itemscope itemtype="http://schema.org/Article" class="post-block home" lang="zh-cn">
    <link itemprop="mainEntityOfPage" href="http://yoursite.com/2020/04/27/Leetcode-No-23-merge-k-sorted-lists/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="image" content="https://blog-bucket-1300756499.cos.ap-chengdu.myqcloud.com/avatar.jpg">
      <meta itemprop="name" content="Cyril Nee">
      <meta itemprop="description" content="站在巨人的肩膀上。">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="子我">
    </span>
      <header class="post-header">
        <h1 class="post-title" itemprop="name headline">
          
            <a href="/2020/04/27/Leetcode-No-23-merge-k-sorted-lists/" class="post-title-link" itemprop="url">Leetcode No.23 merge-k-sorted-lists</a>
        </h1>

        <div class="post-meta">
            <span class="post-meta-item">
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              <span class="post-meta-item-text">Posted on</span>
              

              <time title="Created: 2020-04-27 00:24:52 / Modified: 00:38:06" itemprop="dateCreated datePublished" datetime="2020-04-27T00:24:52+08:00">2020-04-27</time>
            </span>

          
  
  <span class="post-meta-item">
    
      <span class="post-meta-item-icon">
        <i class="fa fa-comment-o"></i>
      </span>
      <span class="post-meta-item-text">Valine: </span>
    
    <a title="valine" href="/2020/04/27/Leetcode-No-23-merge-k-sorted-lists/#comments" itemprop="discussionUrl">
      <span class="post-comments-count valine-comment-count" data-xid="/2020/04/27/Leetcode-No-23-merge-k-sorted-lists/" itemprop="commentCount"></span>
    </a>
  </span>
  
  

        </div>
      </header>

    
    
    
    <div class="post-body" itemprop="articleBody">

      
          <h3 id="描述"><a class="markdownIt-Anchor" href="#描述"></a> 描述</h3>
<p>合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。</p>
<p>示例:</p>
<pre><code>输入:
[
  1-&gt;4-&gt;5,
  1-&gt;3-&gt;4,
  2-&gt;6
]
输出: 1-&gt;1-&gt;2-&gt;3-&gt;4-&gt;4-&gt;5-&gt;6
</code></pre>
<h3 id="思路"><a class="markdownIt-Anchor" href="#思路"></a> 思路</h3>
<p>合并多个有序链表。 本人思路跟合并两个个有序链表是一样的。关键是找到最小的和次小的节点进行合并。 这里维护了个最小堆记录节点值的关系</p>
<p>理想很丰满，现实很骨感。合并的时候遇到了一个问题。同值的时候，不能确定哪个节点应该作为前值。（后面想到了备选方案可以解决这个问题）改了一个写法。cur的next一直连接推出的堆顶最小元素。堆顶推入该元素的下个节点。以此类推</p>
<h3 id="复杂度-onmlogn"><a class="markdownIt-Anchor" href="#复杂度-onmlogn"></a> 复杂度: O(nm*log(n))</h3>
<h3 id="answers-code"><a class="markdownIt-Anchor" href="#answers-code"></a> Answers Code</h3>
<pre><code># Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def mergeKLists(self, lists: List[ListNode]) -&gt; ListNode:
        if not lists:
            return None        
        lists = list(filter(lambda x:x, lists))
        if not lists:
            return None        

        if len(lists) == 1:
            return lists[0]

        # 最小堆
        tree = []

        def getTop():
            if tree:
                return tree[0]

        def add(node:ListNode):
            index = len(tree)
            tree.append(node)

            while index &gt; 0:
                parent = int((index-1)/2)
                if tree[parent].val &lt;= tree[index].val:
                    break
                temp = tree[parent]
                tree[parent] = tree[index]
                tree[index] = temp
                index = parent

        def delete():
            if not tree:
                return
            tree[0] = tree[-1]
            tree.pop()
            if len(tree) &lt; 2:
                return
            index = 0
            while index &lt; int(len(tree) / 2):
                child = index * 2 + 1
                if child &lt; len(tree) - 1 and tree[child].val &gt; tree[child+1].val:
                    child += 1
                if tree[index].val &gt; tree[child].val:
                    temp = tree[index]
                    tree[index] = tree[child]
                    tree[child] = temp
                    index = child
                else:
                    break

        for node in lists:
            add(node)

        res = None
        ans = None

        while True:
            if not tree:
                break
            node1 = getTop()
            delete()
            if not ans:
                ans = node1
                res = node1
                if ans.next:
                    add(ans.next)
            else:
                ans.next = node1
                ans = ans.next
                if node1.next:
                    add(node1.next)

        return res
</code></pre>

      
    </div>

    
    
    
      <footer class="post-footer">
        <div class="post-eof"></div>
      </footer>
  </article>
  
  
  

        
  
  
  <article itemscope itemtype="http://schema.org/Article" class="post-block home" lang="zh-cn">
    <link itemprop="mainEntityOfPage" href="http://yoursite.com/2020/04/25/Leetcode-shortest-supersequence/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="image" content="https://blog-bucket-1300756499.cos.ap-chengdu.myqcloud.com/avatar.jpg">
      <meta itemprop="name" content="Cyril Nee">
      <meta itemprop="description" content="站在巨人的肩膀上。">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="子我">
    </span>
      <header class="post-header">
        <h1 class="post-title" itemprop="name headline">
          
            <a href="/2020/04/25/Leetcode-shortest-supersequence/" class="post-title-link" itemprop="url">Leetcode shortest-supersequence</a>
        </h1>

        <div class="post-meta">
            <span class="post-meta-item">
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              <span class="post-meta-item-text">Posted on</span>
              

              <time title="Created: 2020-04-25 22:51:56 / Modified: 23:20:35" itemprop="dateCreated datePublished" datetime="2020-04-25T22:51:56+08:00">2020-04-25</time>
            </span>

          
  
  <span class="post-meta-item">
    
      <span class="post-meta-item-icon">
        <i class="fa fa-comment-o"></i>
      </span>
      <span class="post-meta-item-text">Valine: </span>
    
    <a title="valine" href="/2020/04/25/Leetcode-shortest-supersequence/#comments" itemprop="discussionUrl">
      <span class="post-comments-count valine-comment-count" data-xid="/2020/04/25/Leetcode-shortest-supersequence/" itemprop="commentCount"></span>
    </a>
  </span>
  
  

        </div>
      </header>

    
    
    
    <div class="post-body" itemprop="articleBody">

      
          <h3 id="描述"><a class="markdownIt-Anchor" href="#描述"></a> 描述</h3>
<p>两个数组，一个长一个短，短的元素均不相同。找到长数组中包含短数组所有的元素的最短子数组，其出现顺序无关紧要。</p>
<p>返回最短子数组的左端点和右端点，如有多个满足条件的子数组，返回左端点最小的一个。若不存在，返回空数组。</p>
<pre><code>示例 1:

输入:
big = [7,5,9,0,2,1,3,5,7,9,1,1,5,8,8,9,7]
small = [1,5,9]
输出: [7,10]
</code></pre>
<h3 id="思路"><a class="markdownIt-Anchor" href="#思路"></a> 思路</h3>
<p>目的是找到短数组在长数组中出现的最短位置。我这里通过一个dictionary记录big中出现的small元素及其位置。 由于记录长度的时候如果同个元素后者出现则以后者为准（前者或已经被统计）。使用队列记录每一个small元素的位置，当对尾的元素位置已经在后面出现过时（即队尾位置跟字典位置不相符时）表示队尾已经无用了，删除之。当字典元素与small元素数量相同时则表示是合法答案。 进行长度判断。</p>
<h3 id="复杂度-on"><a class="markdownIt-Anchor" href="#复杂度-on"></a> 复杂度: O(n)</h3>
<p>队列最大长度为n，且元素只会出现一次。</p>
<h3 id="answers-code"><a class="markdownIt-Anchor" href="#answers-code"></a> Answers Code</h3>
<pre><code>from collections import deque

class Node:
    def __init__(self, val, index):
        self.val = val
        self.index = index


class Solution:
    def shortestSeq(self, big: List[int], small: List[int]) -&gt; List[int]:
        # 双端队列
        q = deque()
        max_index = -1
        min_index = -1
        small = set(small)
        m = {}
        i = 0
        ans = []
        while i &lt; len(big):
            if big[i] in small:
                m[big[i]] = i
                q.append(Node(big[i], i))
                while q[0].index != m[q[0].val]:
                    q.popleft()

            if len(m) == len(small):
                if not ans or ans[1] - ans[0] &gt; q[-1].index - q[0].index:
                    ans = [q[0].index, q[-1].index]

            i += 1
        return ans
</code></pre>

      
    </div>

    
    
    
      <footer class="post-footer">
        <div class="post-eof"></div>
      </footer>
  </article>
  
  
  

        
  
  
  <article itemscope itemtype="http://schema.org/Article" class="post-block home" lang="zh-cn">
    <link itemprop="mainEntityOfPage" href="http://yoursite.com/2020/04/25/Leetcode-No-46-permutations/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="image" content="https://blog-bucket-1300756499.cos.ap-chengdu.myqcloud.com/avatar.jpg">
      <meta itemprop="name" content="Cyril Nee">
      <meta itemprop="description" content="站在巨人的肩膀上。">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="子我">
    </span>
      <header class="post-header">
        <h1 class="post-title" itemprop="name headline">
          
            <a href="/2020/04/25/Leetcode-No-46-permutations/" class="post-title-link" itemprop="url">Leetcode No.46 permutations</a>
        </h1>

        <div class="post-meta">
            <span class="post-meta-item">
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              <span class="post-meta-item-text">Posted on</span>

              <time title="Created: 2020-04-25 22:50:11" itemprop="dateCreated datePublished" datetime="2020-04-25T22:50:11+08:00">2020-04-25</time>
            </span>
              <span class="post-meta-item">
                <span class="post-meta-item-icon">
                  <i class="fa fa-calendar-check-o"></i>
                </span>
                <span class="post-meta-item-text">Edited on</span>
                <time title="Modified: 2020-04-26 21:02:05" itemprop="dateModified" datetime="2020-04-26T21:02:05+08:00">2020-04-26</time>
              </span>

          
  
  <span class="post-meta-item">
    
      <span class="post-meta-item-icon">
        <i class="fa fa-comment-o"></i>
      </span>
      <span class="post-meta-item-text">Valine: </span>
    
    <a title="valine" href="/2020/04/25/Leetcode-No-46-permutations/#comments" itemprop="discussionUrl">
      <span class="post-comments-count valine-comment-count" data-xid="/2020/04/25/Leetcode-No-46-permutations/" itemprop="commentCount"></span>
    </a>
  </span>
  
  

        </div>
      </header>

    
    
    
    <div class="post-body" itemprop="articleBody">

      
          <h3 id="描述"><a class="markdownIt-Anchor" href="#描述"></a> 描述</h3>
<p>4月25日每日一题。给定一个<strong>没有重复</strong>数字的序列，返回其所有可能的全排列。</p>
<pre><code>示例:

输入: [1,2,3]
输出:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]
</code></pre>
<h3 id="思路"><a class="markdownIt-Anchor" href="#思路"></a> 思路</h3>
<p>回溯算法例题。</p>
<h3 id="复杂度-onn"><a class="markdownIt-Anchor" href="#复杂度-onn"></a> 复杂度: O(n^n)</h3>
<h3 id="answers-code"><a class="markdownIt-Anchor" href="#answers-code"></a> Answers Code</h3>
<pre><code>class Solution:
    def permute(self, nums: List[int]) -&gt; List[List[int]]:
        self.res = []
        self.dfs(nums, [0]*len(nums), len(nums), [])
        return self.res
    def dfs(self, nums, used, total, ans):
        if not total:
            self.res.append(ans)
            return
        i = 0
        while i &lt; len(nums):
            if not used[i]:
                used[i] = 1
                self.dfs(nums, used, total - 1, ans + [nums[i]])
                used[i] = 0
            i += 1
</code></pre>

      
    </div>

    
    
    
      <footer class="post-footer">
        <div class="post-eof"></div>
      </footer>
  </article>
  
  
  

        
  
  
  <article itemscope itemtype="http://schema.org/Article" class="post-block home" lang="zh-cn">
    <link itemprop="mainEntityOfPage" href="http://yoursite.com/2020/04/24/leetcode-reverse-order-pair/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="image" content="https://blog-bucket-1300756499.cos.ap-chengdu.myqcloud.com/avatar.jpg">
      <meta itemprop="name" content="Cyril Nee">
      <meta itemprop="description" content="站在巨人的肩膀上。">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="子我">
    </span>
      <header class="post-header">
        <h1 class="post-title" itemprop="name headline">
          
            <a href="/2020/04/24/leetcode-reverse-order-pair/" class="post-title-link" itemprop="url">Leetcode 数组中的逆序对</a>
        </h1>

        <div class="post-meta">
            <span class="post-meta-item">
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              <span class="post-meta-item-text">Posted on</span>
              

              <time title="Created: 2020-04-24 22:29:52 / Modified: 22:53:33" itemprop="dateCreated datePublished" datetime="2020-04-24T22:29:52+08:00">2020-04-24</time>
            </span>

          
  
  <span class="post-meta-item">
    
      <span class="post-meta-item-icon">
        <i class="fa fa-comment-o"></i>
      </span>
      <span class="post-meta-item-text">Valine: </span>
    
    <a title="valine" href="/2020/04/24/leetcode-reverse-order-pair/#comments" itemprop="discussionUrl">
      <span class="post-comments-count valine-comment-count" data-xid="/2020/04/24/leetcode-reverse-order-pair/" itemprop="commentCount"></span>
    </a>
  </span>
  
  

        </div>
      </header>

    
    
    
    <div class="post-body" itemprop="articleBody">

      
          <h3 id="描述"><a class="markdownIt-Anchor" href="#描述"></a> 描述</h3>
<p>在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。</p>
<pre><code>示例 1:

输入: [7,5,6,4]
输出: 5
</code></pre>
<h3 id="思路"><a class="markdownIt-Anchor" href="#思路"></a> 思路</h3>
<p>第一时间想到的是排序后计算偏移量的办法，如果数字不重复时是可行的。如果数值有重复，则位置偏移不能保证后面的值一定比前值要小。</p>
<p>午睡的时候想到用树状数组统计前面的数字有多少个数字比它大就可以了，至于数字范围较大的问题，由于数字一共50000个，直接化为[1,50000]内的数字即可。对于静态查询的题目算是大财小用了，应该还有其他解，一时想不到。但这个解法已经是O(nlogn)了。</p>
<h3 id="复杂度-onlogn"><a class="markdownIt-Anchor" href="#复杂度-onlogn"></a> 复杂度: O(nlog(n))</h3>
<h3 id="answers-code"><a class="markdownIt-Anchor" href="#answers-code"></a> Answers Code</h3>
<pre><code>class Node:
    def __init__(self, val, index):
        self.val = val
        self.index = index

class Solution:

    def reversePairs(self, nums: List[int]) -&gt; int:
        max_index = 65537
        tree = [0] * max_index

        def lowerBit(num):
            return num &amp; (-num)

        def query(index):
            ans = 0
            while index &gt; 0:
                ans += tree[index]
                index -= lowerBit(index)
            return ans

        def add(index, num):
            if index &lt;= 0:
                return 0
            while index &lt; max_index:
                tree[index] += num
                index += lowerBit(index)

        i = 0
        nodes = []

        # 前期处理
        while i &lt; len(nums):
            nodes.append(Node(nums[i], i))
            i += 1
        nodes.sort(key=lambda node:node.val)
        i = 0
        cnt = 1
        while i &lt; len(nums):
            if i &gt; 0 and nodes[i].val &gt; nodes[i-1].val:
                cnt += 1
            nums[nodes[i].index] = cnt
            i += 1

        # print(nums)

        i = len(nums) - 1
        ans = 0
        while i &gt;= 0:
            ans += query(nums[i] - 1)
            # print(query(nums[i] - 1))
            add(nums[i], 1)
            i -= 1
        return ans
</code></pre>

      
    </div>

    
    
    
      <footer class="post-footer">
        <div class="post-eof"></div>
      </footer>
  </article>
  
  
  

        
  
  
  <article itemscope itemtype="http://schema.org/Article" class="post-block home" lang="zh-cn">
    <link itemprop="mainEntityOfPage" href="http://yoursite.com/2020/04/23/leetcode-coin-lcci/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="image" content="https://blog-bucket-1300756499.cos.ap-chengdu.myqcloud.com/avatar.jpg">
      <meta itemprop="name" content="Cyril Nee">
      <meta itemprop="description" content="站在巨人的肩膀上。">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="子我">
    </span>
      <header class="post-header">
        <h1 class="post-title" itemprop="name headline">
          
            <a href="/2020/04/23/leetcode-coin-lcci/" class="post-title-link" itemprop="url">Leetcode coin-lcci/</a>
        </h1>

        <div class="post-meta">
            <span class="post-meta-item">
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              <span class="post-meta-item-text">Posted on</span>

              <time title="Created: 2020-04-23 23:29:29" itemprop="dateCreated datePublished" datetime="2020-04-23T23:29:29+08:00">2020-04-23</time>
            </span>
              <span class="post-meta-item">
                <span class="post-meta-item-icon">
                  <i class="fa fa-calendar-check-o"></i>
                </span>
                <span class="post-meta-item-text">Edited on</span>
                <time title="Modified: 2020-04-24 22:51:05" itemprop="dateModified" datetime="2020-04-24T22:51:05+08:00">2020-04-24</time>
              </span>

          
  
  <span class="post-meta-item">
    
      <span class="post-meta-item-icon">
        <i class="fa fa-comment-o"></i>
      </span>
      <span class="post-meta-item-text">Valine: </span>
    
    <a title="valine" href="/2020/04/23/leetcode-coin-lcci/#comments" itemprop="discussionUrl">
      <span class="post-comments-count valine-comment-count" data-xid="/2020/04/23/leetcode-coin-lcci/" itemprop="commentCount"></span>
    </a>
  </span>
  
  

        </div>
      </header>

    
    
    
    <div class="post-body" itemprop="articleBody">

      
          <h3 id="描述"><a class="markdownIt-Anchor" href="#描述"></a> 描述</h3>
<p>2020年4月23日每日一题。 硬币。给定数量不限的硬币，币值为25分、10分、5分和1分，编写代码计算n分有几种表示法。(结果可能会很大，你需要将结果模上1000000007)</p>
<p>示例:</p>
<pre><code> 输入: n = 5
 输出：2
 解释: 有两种方式可以凑成总金额:
 5=5
 5=1+1+1+1+1
</code></pre>
<h3 id="思路"><a class="markdownIt-Anchor" href="#思路"></a> 思路</h3>
<p>dp完全背包。将面值从小到大排列后假设为可选集合coins（即coins = [1,5,10,25]）。对于前i种硬币，面值j。有兑换次数</p>
<p class='katex-block'><span class="katex-display"><span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>d</mi><mi>p</mi><mo stretchy="false">[</mo><mi>i</mi><mo stretchy="false">]</mo><mo stretchy="false">[</mo><mi>j</mi><mo stretchy="false">]</mo><mo>=</mo><mi>d</mi><mi>p</mi><mo stretchy="false">[</mo><mi>i</mi><mo stretchy="false">]</mo><mo stretchy="false">[</mo><mi>j</mi><mo>−</mo><mi>c</mi><mi>o</mi><mi>i</mi><mi>n</mi><mi>s</mi><mo stretchy="false">[</mo><mi>i</mi><mo stretchy="false">]</mo><mo stretchy="false">]</mo><mo>+</mo><mi>d</mi><mi>p</mi><mo stretchy="false">[</mo><mi>i</mi><mo>−</mo><mn>1</mn><mo stretchy="false">]</mo><mo stretchy="false">[</mo><mi>j</mi><mo stretchy="false">]</mo></mrow><annotation encoding="application/x-tex">dp[i][j] = dp[i][j-coins[i]] + dp[i-1][j]
</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathdefault">d</span><span class="mord mathdefault">p</span><span class="mopen">[</span><span class="mord mathdefault">i</span><span class="mclose">]</span><span class="mopen">[</span><span class="mord mathdefault" style="margin-right:0.05724em;">j</span><span class="mclose">]</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel">=</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathdefault">d</span><span class="mord mathdefault">p</span><span class="mopen">[</span><span class="mord mathdefault">i</span><span class="mclose">]</span><span class="mopen">[</span><span class="mord mathdefault" style="margin-right:0.05724em;">j</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">−</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathdefault">c</span><span class="mord mathdefault">o</span><span class="mord mathdefault">i</span><span class="mord mathdefault">n</span><span class="mord mathdefault">s</span><span class="mopen">[</span><span class="mord mathdefault">i</span><span class="mclose">]</span><span class="mclose">]</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">+</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathdefault">d</span><span class="mord mathdefault">p</span><span class="mopen">[</span><span class="mord mathdefault">i</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">−</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord">1</span><span class="mclose">]</span><span class="mopen">[</span><span class="mord mathdefault" style="margin-right:0.05724em;">j</span><span class="mclose">]</span></span></span></span></span></p>
<h3 id="复杂度-on-空间-on"><a class="markdownIt-Anchor" href="#复杂度-on-空间-on"></a> 复杂度: O(n) ，空间 O(n)</h3>
<p>背包中硬币种类为常数。 空间进行优化压缩，只需要n的列表即可</p>
<h3 id="answers-code"><a class="markdownIt-Anchor" href="#answers-code"></a> Answers Code</h3>
<pre><code>class Solution:
    def waysToChange(self, n: int) -&gt; int:
        dp = [0] * (n+1)
        dp[0] = 1
        coins = [1, 5, 10, 25]
        # dp[n] = (dp[n] + dp[n-coins[i]]) % K
        for coin in coins:
            i = 0
            while i &lt;= n - coin:
                dp[i+coin] += dp[i]
                dp[i+coin] %= 1000000007
                i += 1
        return dp[n]
</code></pre>

      
    </div>

    
    
    
      <footer class="post-footer">
        <div class="post-eof"></div>
      </footer>
  </article>
  
  
  

        
  
  
  <article itemscope itemtype="http://schema.org/Article" class="post-block home" lang="zh-cn">
    <link itemprop="mainEntityOfPage" href="http://yoursite.com/2020/04/22/Leetcode-No-199-binary-tree-right-side-view/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="image" content="https://blog-bucket-1300756499.cos.ap-chengdu.myqcloud.com/avatar.jpg">
      <meta itemprop="name" content="Cyril Nee">
      <meta itemprop="description" content="站在巨人的肩膀上。">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="子我">
    </span>
      <header class="post-header">
        <h1 class="post-title" itemprop="name headline">
          
            <a href="/2020/04/22/Leetcode-No-199-binary-tree-right-side-view/" class="post-title-link" itemprop="url">Leetcode No.199 binary tree right side view</a>
        </h1>

        <div class="post-meta">
            <span class="post-meta-item">
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              <span class="post-meta-item-text">Posted on</span>

              <time title="Created: 2020-04-22 17:46:27" itemprop="dateCreated datePublished" datetime="2020-04-22T17:46:27+08:00">2020-04-22</time>
            </span>
              <span class="post-meta-item">
                <span class="post-meta-item-icon">
                  <i class="fa fa-calendar-check-o"></i>
                </span>
                <span class="post-meta-item-text">Edited on</span>
                <time title="Modified: 2020-04-24 22:51:04" itemprop="dateModified" datetime="2020-04-24T22:51:04+08:00">2020-04-24</time>
              </span>

          
  
  <span class="post-meta-item">
    
      <span class="post-meta-item-icon">
        <i class="fa fa-comment-o"></i>
      </span>
      <span class="post-meta-item-text">Valine: </span>
    
    <a title="valine" href="/2020/04/22/Leetcode-No-199-binary-tree-right-side-view/#comments" itemprop="discussionUrl">
      <span class="post-comments-count valine-comment-count" data-xid="/2020/04/22/Leetcode-No-199-binary-tree-right-side-view/" itemprop="commentCount"></span>
    </a>
  </span>
  
  

        </div>
      </header>

    
    
    
    <div class="post-body" itemprop="articleBody">

      
          <h3 id="描述"><a class="markdownIt-Anchor" href="#描述"></a> 描述</h3>
<p>2020年4月22日每日一题：给定一棵二叉树，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。</p>
<p>示例:</p>
<pre><code>输入: [1,2,3,null,5,null,4]
输出: [1, 3, 4]
解释:

   1            &lt;---
 /   \
2     3         &lt;---
 \     \
  5     4       &lt;---
</code></pre>
<h3 id="思路"><a class="markdownIt-Anchor" href="#思路"></a> 思路</h3>
<p>题目较为简单，右侧深搜即可。全局使用列表保存对应深度下出现的第一个元素即为答案</p>
<h3 id="复杂度-on"><a class="markdownIt-Anchor" href="#复杂度-on"></a> 复杂度: O(n)</h3>
<h3 id="answers-code"><a class="markdownIt-Anchor" href="#answers-code"></a> Answers Code</h3>
<pre><code># Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def __init__(self):
        self.ans = []

    def rightSideView(self, root: TreeNode) -&gt; List[int]:
        if not root :
            return []
        self.rightDfs(root, 0);
        return self.ans

    def rightDfs(self, root: TreeNode, depth: int):
        if not root:
            return
        if depth &gt;= len(self.ans):
            self.ans.append(root.val)
        self.rightDfs(root.right, depth+1)
        self.rightDfs(root.left, depth+1)
</code></pre>

      
    </div>

    
    
    
      <footer class="post-footer">
        <div class="post-eof"></div>
      </footer>
  </article>
  
  
  

        
  
  
  <article itemscope itemtype="http://schema.org/Article" class="post-block home" lang="zh-cn">
    <link itemprop="mainEntityOfPage" href="http://yoursite.com/2020/04/22/Leetcode-No-864-shortest-path-to-get-all-keys/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="image" content="https://blog-bucket-1300756499.cos.ap-chengdu.myqcloud.com/avatar.jpg">
      <meta itemprop="name" content="Cyril Nee">
      <meta itemprop="description" content="站在巨人的肩膀上。">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="子我">
    </span>
      <header class="post-header">
        <h1 class="post-title" itemprop="name headline">
          
            <a href="/2020/04/22/Leetcode-No-864-shortest-path-to-get-all-keys/" class="post-title-link" itemprop="url">Leetcode No.864 shortest path to get all keys.</a>
        </h1>

        <div class="post-meta">
            <span class="post-meta-item">
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              <span class="post-meta-item-text">Posted on</span>

              <time title="Created: 2020-04-22 17:23:49" itemprop="dateCreated datePublished" datetime="2020-04-22T17:23:49+08:00">2020-04-22</time>
            </span>
              <span class="post-meta-item">
                <span class="post-meta-item-icon">
                  <i class="fa fa-calendar-check-o"></i>
                </span>
                <span class="post-meta-item-text">Edited on</span>
                <time title="Modified: 2020-04-24 22:51:01" itemprop="dateModified" datetime="2020-04-24T22:51:01+08:00">2020-04-24</time>
              </span>

          
  
  <span class="post-meta-item">
    
      <span class="post-meta-item-icon">
        <i class="fa fa-comment-o"></i>
      </span>
      <span class="post-meta-item-text">Valine: </span>
    
    <a title="valine" href="/2020/04/22/Leetcode-No-864-shortest-path-to-get-all-keys/#comments" itemprop="discussionUrl">
      <span class="post-comments-count valine-comment-count" data-xid="/2020/04/22/Leetcode-No-864-shortest-path-to-get-all-keys/" itemprop="commentCount"></span>
    </a>
  </span>
  
  

        </div>
      </header>

    
    
    
    <div class="post-body" itemprop="articleBody">

      
          <h3 id="描述"><a class="markdownIt-Anchor" href="#描述"></a> 描述</h3>
<p>给定一个二维网格 grid。 “.” 代表一个空房间， “#” 代表一堵墙， “@” 是起点，（“a”, “b”, …）代表钥匙，（“A”, “B”, …）代表锁。</p>
<p>我们从起点开始出发，一次移动是指向四个基本方向之一行走一个单位空间。我们不能在网格外面行走，也无法穿过一堵墙。如果途经一个钥匙，我们就把它捡起来。除非我们手里有对应的钥匙，否则无法通过锁。</p>
<p>假设 K 为钥匙/锁的个数，且满足 1 &lt;= K &lt;= 6，字母表中的前 K 个字母在网格中都有自己对应的一个小写和一个大写字母。换言之，每个锁有唯一对应的钥匙，每个钥匙也有唯一对应的锁。另外，代表钥匙和锁的字母互为大小写并按字母顺序排列。</p>
<p>返回获取所有钥匙所需要的移动的最少次数。如果无法获取所有钥匙，返回 -1 。</p>
<p>其中：</p>
<ol>
<li>1 &lt;= grid.length &lt;= 30</li>
<li>1 &lt;= grid[0].length &lt;= 30</li>
<li>grid[i][j] 只含有 ‘.’, ‘#’, ‘@’, ‘a’-‘f’ 以及 ‘A’-‘F’<br />
钥匙的数目范围是 [1, 6]，每个钥匙都对应一个不同的字母，正好打开一个对应的锁。</li>
</ol>
<h3 id="思路"><a class="markdownIt-Anchor" href="#思路"></a> 思路</h3>
<p>一开始看到题目可以想到也许可以使用搜索解决。又因数字方位进一步验证了我的猜想。如思路如下：</p>
<ol>
<li>先确定K，使用深搜递归出一个钥匙获取顺序。如 “acbdef”</li>
<li>根据获取顺序。从起点开始进行多次广搜 a =&gt; c  =&gt; b =&gt; d  =&gt; e  =&gt; f计算出一共的最短距离。</li>
<li>广搜过程中遇墙则结束，遇到锁则判断钥匙是否已经在之前拿过了即为通过。</li>
<li>最短距离取最小值。</li>
</ol>
<h3 id="复杂度-okknm"><a class="markdownIt-Anchor" href="#复杂度-okknm"></a> 复杂度: O(K!K*nm)</h3>
<p>由于K&lt;=6，k!最大值为720。单次广搜最坏情况为NM(30*30)，该解法最坏情况3,888,000</p>
<h3 id="answers-code"><a class="markdownIt-Anchor" href="#answers-code"></a> Answers Code</h3>
<pre><code>class Solution {

    // 广搜节点  定义横坐标 纵坐标 和 步数
    static class Loc {
        public int x;
        public int y;
        public int step;

        @Override
        public boolean equals(Object obj) {
            if (!(obj instanceof Loc))
                return super.equals(obj);
            Loc loc = (Loc) obj;
            return this.x == loc.x &amp;&amp; this.y == loc.y;
        }

        @Override
        public int hashCode() {
            return this.x * 40 + this.y;
        }

        public Loc(int x, int y, int step) {
            this.x = x;
            this.y = y;
            this.step = step;
        }

        public Loc(int x, int y) {
            this(x, y, 0);
        }
    }

    final static Loc[] dir = new Loc[]{new Loc(0, 1), new Loc(1, 0), new Loc(0, -1), new Loc(-1, 0)};

    public int shortestPathAllKeys(String[] grid) {
        Character kChar = null;
        for (int i = 0; i &lt; grid.length; i++) {
            for (int j = 0; j &lt; grid[i].length(); j++) {
                if (grid[i].charAt(j) &lt;= 'z' &amp;&amp; grid[i].charAt(j) &gt;= 'a') {
                    if (kChar == null || kChar &lt; grid[i].charAt(j))
                        kChar = grid[i].charAt(j);
                }
            }
        }

        return this.work(0, kChar - 'a' + 1, Collections.emptySet(), &quot;&quot;, grid);

    }

    public int work(int cur, int maxDeep, Set&lt;Character&gt; had, String aim, String[] grid) {

        // 递归到最后一层。 开始for循环广搜处理
        if (cur == maxDeep) {
            char startChar = '@';
            int total = 0;
            Loc startLoc = new Loc(0, 0, 0);
            had = new HashSet&lt;&gt;();
            for (int k = 0; k &lt; maxDeep; k++) {
                changeLocStart(startLoc, startChar, grid);
                startLoc.step = total;
                int temp = bfs(grid, startLoc, had, aim.charAt(k));
                if (temp == -1) {
                    return -1;
                }
                total = temp;
                had.add(aim.charAt(k));
                startChar = aim.charAt(k);
            }
            return total;

        }
        int max = Integer.MAX_VALUE;
        for (char i = 'a'; i &lt; 'a' + maxDeep; i++) {
            if (had.contains(i))
                continue;
            Set&lt;Character&gt; newHad = new HashSet&lt;&gt;(had);
            newHad.add(i);
            int r = work(cur + 1, maxDeep, newHad, aim + i, grid);
            if (r != -1) {
                max = Math.min(max, r);
            }
        }
        return max == Integer.MAX_VALUE ? -1 : max;
    }

    private void changeLocStart(Loc startLoc, char target, String[] grid) {
        for (int i = 0; i &lt; grid.length; i++) {
            for (int j = 0; j &lt; grid[i].length(); j++) {
                if (grid[i].charAt(j) == target) {
                    startLoc.x = i;
                    startLoc.y = j;
                    return;
                }
            }
        }
    }

    // 广搜，查询起点到终点
    private int bfs(String[] grid, Loc start, Set&lt;Character&gt; had, Character target) {
        Queue&lt;Loc&gt; q = new LinkedList&lt;&gt;();
        Set&lt;Loc&gt; used = new HashSet&lt;&gt;();

        q.offer(start);

        while (!q.isEmpty()) {
            Loc front = q.poll();
            if (used.contains(front)) {
                continue;
            }
            used.add(front);
            if (grid[front.x].charAt(front.y) == target)
                return front.step;

            for (int i = 0; i &lt; dir.length; i++) {
                Loc nxt = new Loc(front.x + dir[i].x, front.y + dir[i].y, front.step + 1);

                if (nxt.x &lt; 0 || nxt.x &gt;= grid.length || nxt.y &lt; 0 || nxt.y &gt;= grid[0].length()) {
                    continue;
                }

                if (grid[nxt.x].charAt(nxt.y) == '#')
                    continue;
                else if (grid[nxt.x].charAt(nxt.y) == '.' || grid[nxt.x].charAt(nxt.y)== '@'
                        || (grid[nxt.x].charAt(nxt.y) &gt;= 'a' &amp;&amp; grid[nxt.x].charAt(nxt.y) &lt;= 'z')) {
                    q.offer(nxt);
                } else if (grid[nxt.x].charAt(nxt.y) &gt;= 'A' &amp;&amp; grid[nxt.x].charAt(nxt.y) &lt;= 'Z') {
                    Character need = (char) (grid[nxt.x].charAt(nxt.y) - ('Z' - 'z'));
                    if (!had.contains(need)) {
                        continue;
                    }
                    q.offer(nxt);
                }

            }
        }
        return -1;

    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(&quot;case 1&quot;);
        System.out.println(solution.shortestPathAllKeys(new String[]{&quot;@.a.#&quot;,&quot;###.#&quot;,&quot;b.A.B&quot;}));
        System.out.println(&quot;case 2&quot;);
        System.out.println(solution.shortestPathAllKeys(new String[]{&quot;@..aA&quot;,&quot;..B#.&quot;,&quot;....b&quot;}));
    }
}
//leetcode submit region end(Prohibit modification and deletion)
</code></pre>

      
    </div>

    
    
    
      <footer class="post-footer">
        <div class="post-eof"></div>
      </footer>
  </article>
  
  
  

        
  
  
  <article itemscope itemtype="http://schema.org/Article" class="post-block home" lang="zh-cn">
    <link itemprop="mainEntityOfPage" href="http://yoursite.com/2019/11/24/%E7%BA%A2%E9%BB%91%E6%A0%91/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="image" content="https://blog-bucket-1300756499.cos.ap-chengdu.myqcloud.com/avatar.jpg">
      <meta itemprop="name" content="Cyril Nee">
      <meta itemprop="description" content="站在巨人的肩膀上。">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="子我">
    </span>
      <header class="post-header">
        <h1 class="post-title" itemprop="name headline">
          
            <a href="/2019/11/24/%E7%BA%A2%E9%BB%91%E6%A0%91/" class="post-title-link" itemprop="url">红黑树</a>
        </h1>

        <div class="post-meta">
            <span class="post-meta-item">
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              <span class="post-meta-item-text">Posted on</span>
              

              <time title="Created: 2019-11-24 03:03:05 / Modified: 17:41:48" itemprop="dateCreated datePublished" datetime="2019-11-24T03:03:05+08:00">2019-11-24</time>
            </span>

          
  
  <span class="post-meta-item">
    
      <span class="post-meta-item-icon">
        <i class="fa fa-comment-o"></i>
      </span>
      <span class="post-meta-item-text">Valine: </span>
    
    <a title="valine" href="/2019/11/24/%E7%BA%A2%E9%BB%91%E6%A0%91/#comments" itemprop="discussionUrl">
      <span class="post-comments-count valine-comment-count" data-xid="/2019/11/24/%E7%BA%A2%E9%BB%91%E6%A0%91/" itemprop="commentCount"></span>
    </a>
  </span>
  
  

        </div>
      </header>

    
    
    
    <div class="post-body" itemprop="articleBody">

      
          <h2 id="红黑树"><a class="markdownIt-Anchor" href="#红黑树"></a> 红黑树</h2>
<p>我们都知道平衡二叉查找树（排序树）在极端情况下，查询效率为O(N)。因此需要一个自平衡的数据结构保证查找效率。本片主角红黑树树就这样诞生了。</p>
<blockquote>
<p>红黑树（英语：Red–black tree）是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，典型的用途是实现关联数组。它在1972年由鲁道夫·贝尔发明，被称为&quot;对称二叉B树&quot;，它现代的名字源于Leo J. Guibas和Robert Sedgewick于1978年写的一篇论文。红黑树的结构复杂，但它的操作有着良好的最坏情况运行时间，并且在实践中高效：它可以在log n时间内完成查找，插入和删除，这里的n是树中元素的数目.</p>
<p>—— 摘自wiki对红黑树的介绍</p>
</blockquote>
<h3 id="性质"><a class="markdownIt-Anchor" href="#性质"></a> 性质</h3>
<p>红黑树是一颗查询复杂度保持在O(log N) 的自平衡二叉查找树。在原有的二叉查找树的性质下，通过给节点上色满足如下性质实现：</p>
<ul>
<li><strong>节点是红色或黑色。</strong></li>
<li><strong>根是黑色。</strong></li>
<li><strong>所有叶子都是黑色（叶子节点指NIL节点）。</strong></li>
<li><strong>每个红色节点必须有两个黑色的子节点。（从每个叶子到根的所有路径上不能有两个连续的红色节点。）</strong></li>
<li><strong>从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。</strong></li>
</ul>
<p>具体的某个红黑树入大概入下图所示。 注意<strong>任何红黑树都要满足上面五条性质。</strong></p>
<p><img src="https://blog-bucket-1300756499.cos.ap-chengdu.myqcloud.com/%E7%BA%A2%E9%BB%91%E6%A0%91.png" alt="" /></p>
<h3 id="操作"><a class="markdownIt-Anchor" href="#操作"></a> 操作</h3>
<p>红黑树的操作包括新增、删除、和查询操作。 查询操作与之前的二叉树查找树雷同，这里略过。额外地，需要说明一下二叉查找树中的旋转操作</p>
<h4 id="旋转"><a class="markdownIt-Anchor" href="#旋转"></a> 旋转</h4>
<p>二叉排序树的旋转指的是不破坏二叉树性质的情况下，改变树的结构的一种操作。具体分为如下两种操作：</p>
<ul>
<li>左旋， 将树进行逆时针旋转。如图所示，节点E进行左旋，原本E的右子树接替E的位置称为父亲，E成为S节点的左孩子。注意如果S原本有左子树（左子树的值应该在E到S之间），将该树称为E的新右儿子。仍然满足二叉排序树的规则：</li>
</ul>
<p><img src="https://blog-bucket-1300756499.cos.ap-chengdu.myqcloud.com/rotationLeft.gif" alt="" /></p>
<ul>
<li>右旋，将树进行顺时针旋转。左旋的镜像操作。如图所示：</li>
</ul>
<p><img src="https://blog-bucket-1300756499.cos.ap-chengdu.myqcloud.com/rotationRight.gif" alt="" /></p>
<p>注意，旋转是满足二叉排序树的结构变化操作。 旋转后的节点高度可能会发生变化。 红黑树而言，可能会导致与其性质冲突。 因此需要再对红黑树进行重染色。</p>
<h4 id="新增"><a class="markdownIt-Anchor" href="#新增"></a> 新增</h4>
<p>红黑树新增时，默认新增的是红色节点。一种情况是，如果节点是根结点，则将树染红即可；一种简单的情况是，当节点的父亲是黑色节点时显然不会违反之前的规则。当父亲节点是红色节点时。需要分情况讨论。</p>
<ol>
<li>
<p>当节点的叔叔节点（父亲节点的兄弟节点）是红色时。 将父亲节点和叔叔节点染黑，将爷爷节点染红。这样操作后，所有经过父亲节点和叔叔节点黑色节点数不变，满足<strong>性质5</strong>，但爷爷节点染红后可能会导致它其与上层节点的冲突。因此当前指针指向爷爷节点，重新进行一次判断。<br />
<img src="https://blog-bucket-1300756499.cos.ap-chengdu.myqcloud.com/%E7%BA%A2%E9%BB%91%E6%A0%91%E6%8F%92%E5%85%A51.png" alt="" /></p>
</li>
<li>
<p>当前节点的叔叔节点为黑色时，分如下两种情况来讨论（这里以父亲节点为左子树来判断，若是右子树则镜像操作即可）</p>
<ol>
<li>
<p>当前节点是父亲节点的左子树。 则将父亲节点染黑，爷爷节点染红。 再对爷爷进行右旋操作。 此时经过父亲节点的节点和黑节点数不变（满足<strong>性质5</strong>）。<br />
<img src="https://blog-bucket-1300756499.cos.ap-chengdu.myqcloud.com/%E7%BA%A2%E9%BB%91%E6%A0%91%E6%8F%92%E5%85%A5%202.1.png" alt="" /></p>
</li>
<li>
<p>当前节点是父亲节点的右子树。则将父亲节点进行左旋，当前指针指向原来的父节点。此时当前节点变为父亲节点的左子树。 按照 2.1 的方式处理。<br />
<img src="https://blog-bucket-1300756499.cos.ap-chengdu.myqcloud.com/%E7%BA%A2%E9%BB%91%E6%A0%91%E6%8F%92%E5%85%A5%202.2.png" alt="" /></p>
</li>
</ol>
</li>
</ol>
<h4 id="删除"><a class="markdownIt-Anchor" href="#删除"></a> 删除</h4>
<p>删除操作比较复杂。 大概跟味两部分：删除流程和删除节点后平衡操作。</p>
<h5 id="删除流程"><a class="markdownIt-Anchor" href="#删除流程"></a> 删除流程</h5>
<p>首先通过二分操作找到需要删除的节点。根据当前节点判断是否能删除：</p>
<ol>
<li>如果被删除节点有两个孩子：直接寻找该节点的中序后继（即右子树中最小的节点）。后继节点的值覆盖当前节点值。指针指向后继重新进行判断。</li>
<li>如果被删除节点有一个孩子或孩子都为 NIL：则继续进行判断</li>
<li>如果被删除节点是红色节点：直接将孩子节点顶替当前节点。不会影响到性质。</li>
<li>如果被删除节点是黑色节点，且其孩子节点为红色：将孩子节点顶替当前节点，再讲孩子节点染黑即可。</li>
<li>如果被删除节点是黑色节点，且孩子节点都为黑色（此时孩子节点必为NIL节点，否则单独节点为黑色不满足性质5）：当时情况较为复杂，则进行以下删除后平衡操作。</li>
</ol>
<h5 id="删除后平衡操作"><a class="markdownIt-Anchor" href="#删除后平衡操作"></a> 删除后平衡操作</h5>
<p>首先是如果当前节点已经是根结点了，则将根结点染黑。</p>
<p>我们将删除前的节点定义为N（先平衡，再删除替换节点），节点的父节点为P， 兄弟节点为S，兄弟节点的左子树为SL，右子树为SR。我们遍历N、P、S、SL、SR可能有的情况有如下几种，我们将主意进行讨论。（下文将由N节点为P节点的左子树进行讨论。若为右子树，镜像操作即可）</p>
<table>
<thead>
<tr>
<th>N</th>
<th>P</th>
<th>S</th>
<th>SL</th>
<th>SR</th>
<th>case</th>
</tr>
</thead>
<tbody>
<tr>
<td>B</td>
<td>S</td>
<td>B</td>
<td>B(NIL)</td>
<td>B(NIL)</td>
<td>(1)</td>
</tr>
<tr>
<td>B</td>
<td>B</td>
<td>B</td>
<td>B(NIL)</td>
<td>B(NIL)</td>
<td>(2)</td>
</tr>
<tr>
<td>B</td>
<td>B</td>
<td>S</td>
<td>B</td>
<td>B</td>
<td>(3)</td>
</tr>
<tr>
<td>B</td>
<td>B(or S)</td>
<td>B</td>
<td>S</td>
<td>B(NIL)</td>
<td>(4)</td>
</tr>
<tr>
<td>B</td>
<td>B(or S)</td>
<td>B</td>
<td>S(or B(NIL))</td>
<td>S</td>
<td>(5)</td>
</tr>
</tbody>
</table>
<ol>
<li>
<p>删除节点为黑色， 父亲节点为红色， S节点为黑色， 且S节点的孩子SL、SR都为黑色（NIL节点）。 则将P节点染黑，S节点染红。则经过S节点的黑色节点数不变。经过N的黑色节点数补齐。满足相关性质。<br />
<img src="https://blog-bucket-1300756499.cos.ap-chengdu.myqcloud.com/%E7%BA%A2%E9%BB%91%E6%A0%91%E5%88%A0%E9%99%A4%201.png" alt="" /></p>
</li>
<li>
<p>删除节点为黑色， 父亲节点为黑色， S节点为黑色， 且S节点的孩子SL、SR都为黑色（NIL节点）。将S节点染红。此时通过N节点和通过S节节点，即通过P的比删除前少1。将当前指针指向P节点，重新执行平衡操作。<br />
<img src="https://blog-bucket-1300756499.cos.ap-chengdu.myqcloud.com/%E7%BA%A2%E9%BB%91%E6%A0%91%E5%88%A0%E9%99%A4%202.png" alt="" /></p>
</li>
<li>
<p>删除节点为黑色，父亲节点为黑色，S节点为红色，则S节点的孩子SL、SR都为黑色。将P节点染红，S节点染黑，再对叶子节点进行左旋。此时经过S节点的数量不变。经过N的节点仍然少1，此时P为红色。按照情况4、5进行判断。<br />
<img src="https://blog-bucket-1300756499.cos.ap-chengdu.myqcloud.com/%E7%BA%A2%E9%BB%91%E6%A0%91%E5%88%A0%E9%99%A4%203.png" alt="" /></p>
</li>
<li>
<p>删除节点为黑色，父亲节点为红色或者为黑色，S节点为黑色，其左SL节点为红色，右节点为黑色（为NIL）。将SL染黑，S染红，S节点右旋。这样S和SL角色互换，可以按照情况5判断。<br />
<img src="https://blog-bucket-1300756499.cos.ap-chengdu.myqcloud.com/%E7%BA%A2%E9%BB%91%E6%A0%91%E5%88%A0%E9%99%A44.png" alt="" /></p>
</li>
<li>
<p>删除节点为黑色，父亲节点为红色或者黑色，S节点为黑色。其右子树SR为红色（SL为红色或黑（NIL））。S节点染为P节点的颜色，P节点染黑，SR节点染黑，P节点左旋。 此时SR节点不变， SL节点和N节点恢复。满足规律5。恢复平衡。<br />
<img src="https://blog-bucket-1300756499.cos.ap-chengdu.myqcloud.com/%E7%BA%A2%E9%BB%91%E6%A0%91%E5%88%A0%E9%99%A45.png" alt="" /></p>
</li>
</ol>
<h3 id="证明"><a class="markdownIt-Anchor" href="#证明"></a> 证明</h3>
<p>我们在之前说过红黑树的查询效率是log2(n)。但具体为什么根据前面5条性质即确定红黑树的具体查询效率的呢？需要进行证明：</p>
<p>首先定义 BH(v) 为节点黑色高度（ 红黑树的节点v上到他的叶子节点的黑色节点的个数，不计v本身）、TOTAL[ BH(v) ] 为 当黑高为 BH(v 时，树可能有的总叶子节点个数 可知</p>
<ol>
<li>
<p>BH(v) = 0 时 v 此时可能为空节点或只有v本身 、TOTAL[ BH(v) ] 最小为 0</p>
</li>
<li>
<p>当 BH(v) &gt; 0 时： 根据 <strong>性质5</strong> 黑高为 BH(V) 的 红黑树， 其子树的黑高至少为 BH(V) - 1 （或子树的高度仍为 BH(V) ）即数的节点总数</p>
</li>
</ol>
<p class='katex-block'><span class="katex-display"><span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>T</mi><mi>O</mi><mi>T</mi><mi>A</mi><mi>L</mi><mo stretchy="false">[</mo><mi>B</mi><mi>H</mi><mo stretchy="false">(</mo><mi>v</mi><mo stretchy="false">)</mo><mo stretchy="false">]</mo><mo>≥</mo><mn>2</mn><mo>⋅</mo><mi>T</mi><mi>O</mi><mi>T</mi><mi>A</mi><mi>L</mi><mo stretchy="false">[</mo><mi>B</mi><mi>H</mi><mo stretchy="false">(</mo><mi>v</mi><mo stretchy="false">)</mo><mo>−</mo><mn>1</mn><mo stretchy="false">]</mo><mo>+</mo><mn>1</mn></mrow><annotation encoding="application/x-tex">TOTAL[BH(v)] \geq 2 \cdot TOTAL[BH(v) - 1] + 1
</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathdefault" style="margin-right:0.13889em;">T</span><span class="mord mathdefault" style="margin-right:0.02778em;">O</span><span class="mord mathdefault" style="margin-right:0.13889em;">T</span><span class="mord mathdefault">A</span><span class="mord mathdefault">L</span><span class="mopen">[</span><span class="mord mathdefault" style="margin-right:0.05017em;">B</span><span class="mord mathdefault" style="margin-right:0.08125em;">H</span><span class="mopen">(</span><span class="mord mathdefault" style="margin-right:0.03588em;">v</span><span class="mclose">)</span><span class="mclose">]</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel">≥</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:0.64444em;vertical-align:0em;"></span><span class="mord">2</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">⋅</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathdefault" style="margin-right:0.13889em;">T</span><span class="mord mathdefault" style="margin-right:0.02778em;">O</span><span class="mord mathdefault" style="margin-right:0.13889em;">T</span><span class="mord mathdefault">A</span><span class="mord mathdefault">L</span><span class="mopen">[</span><span class="mord mathdefault" style="margin-right:0.05017em;">B</span><span class="mord mathdefault" style="margin-right:0.08125em;">H</span><span class="mopen">(</span><span class="mord mathdefault" style="margin-right:0.03588em;">v</span><span class="mclose">)</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">−</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord">1</span><span class="mclose">]</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">+</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:0.64444em;vertical-align:0em;"></span><span class="mord">1</span></span></span></span></span></p>
<p>由此可得</p>
<p class='katex-block'><span class="katex-display"><span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>T</mi><mi>O</mi><mi>T</mi><mi>A</mi><mi>L</mi><mo stretchy="false">[</mo><mi>B</mi><mi>H</mi><mo stretchy="false">(</mo><mi>v</mi><mo stretchy="false">)</mo><mo stretchy="false">]</mo><mo>=</mo><msup><mn>2</mn><mrow><mi>B</mi><mi>H</mi><mo stretchy="false">(</mo><mi>v</mi><mo stretchy="false">)</mo></mrow></msup><mo>−</mo><mn>1</mn></mrow><annotation encoding="application/x-tex">TOTAL[BH(v)] = 2^{BH(v)} - 1
</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathdefault" style="margin-right:0.13889em;">T</span><span class="mord mathdefault" style="margin-right:0.02778em;">O</span><span class="mord mathdefault" style="margin-right:0.13889em;">T</span><span class="mord mathdefault">A</span><span class="mord mathdefault">L</span><span class="mopen">[</span><span class="mord mathdefault" style="margin-right:0.05017em;">B</span><span class="mord mathdefault" style="margin-right:0.08125em;">H</span><span class="mopen">(</span><span class="mord mathdefault" style="margin-right:0.03588em;">v</span><span class="mclose">)</span><span class="mclose">]</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel">=</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:1.0213299999999998em;vertical-align:-0.08333em;"></span><span class="mord"><span class="mord">2</span><span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist" style="height:0.938em;"><span style="top:-3.113em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight"><span class="mord mathdefault mtight" style="margin-right:0.05017em;">B</span><span class="mord mathdefault mtight" style="margin-right:0.08125em;">H</span><span class="mopen mtight">(</span><span class="mord mathdefault mtight" style="margin-right:0.03588em;">v</span><span class="mclose mtight">)</span></span></span></span></span></span></span></span></span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">−</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:0.64444em;vertical-align:0em;"></span><span class="mord">1</span></span></span></span></span></p>
<p>因此BH(V) 跟 TOTAL[V] 之间满足指数关系。又由<strong>性质4</strong>可知，树的黑高至少为这棵树的二分之一。 即 BH(V) &gt;= H(V) / 2，可得，对于根结点root而言。有</p>
<p class='katex-block'><span class="katex-display"><span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>n</mi><mo>≥</mo><msup><mn>2</mn><mrow><mi>B</mi><mi>H</mi><mo stretchy="false">(</mo><mi>r</mi><mi>o</mi><mi>o</mi><mi>t</mi><mo stretchy="false">)</mo></mrow></msup><mo>−</mo><mn>1</mn><mo>=</mo><mo>&gt;</mo><mi>n</mi><mo>≥</mo><msup><mn>2</mn><mrow><mi>H</mi><mo stretchy="false">(</mo><mi>r</mi><mi>o</mi><mi>o</mi><mi>t</mi><mo stretchy="false">)</mo><mo>÷</mo><mn>2</mn></mrow></msup><mo>−</mo><mn>1</mn><mo>=</mo><mo>&gt;</mo><mi>n</mi><mo>+</mo><mn>1</mn><mo>≥</mo><msup><mn>2</mn><mrow><mi>H</mi><mo stretchy="false">(</mo><mi>r</mi><mi>o</mi><mi>o</mi><mi>t</mi><mo stretchy="false">)</mo><mo>÷</mo><mn>2</mn></mrow></msup><mo>=</mo><mo>&gt;</mo><mi>l</mi><mi>o</mi><msub><mi>g</mi><mn>2</mn></msub><mo stretchy="false">(</mo><mi>n</mi><mo>+</mo><mn>1</mn><mo stretchy="false">)</mo><mo>≥</mo><mi>H</mi><mo stretchy="false">(</mo><mi>r</mi><mi>o</mi><mi>o</mi><mi>t</mi><mo stretchy="false">)</mo><mo>÷</mo><mn>2</mn><mo>=</mo><mo>&gt;</mo><mi>H</mi><mo stretchy="false">(</mo><mi>r</mi><mi>o</mi><mi>o</mi><mi>t</mi><mo stretchy="false">)</mo><mo>≤</mo><mn>2</mn><mo>⋅</mo><mi>l</mi><mi>o</mi><msub><mi>g</mi><mn>2</mn></msub><mo stretchy="false">(</mo><mi>n</mi><mo>+</mo><mn>1</mn><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">
n \geq 2^{BH(root)} - 1

=&gt; n \geq 2^{H(root) \div 2} - 1

=&gt; n + 1 \geq 2^{H(root) \div 2}

=&gt; log_2(n + 1) \geq H(root) \div 2

=&gt;  H(root) \leq 2 \cdot log_2(n + 1)

</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.7719400000000001em;vertical-align:-0.13597em;"></span><span class="mord mathdefault">n</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel">≥</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:1.0213299999999998em;vertical-align:-0.08333em;"></span><span class="mord"><span class="mord">2</span><span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist" style="height:0.938em;"><span style="top:-3.113em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight"><span class="mord mathdefault mtight" style="margin-right:0.05017em;">B</span><span class="mord mathdefault mtight" style="margin-right:0.08125em;">H</span><span class="mopen mtight">(</span><span class="mord mathdefault mtight" style="margin-right:0.02778em;">r</span><span class="mord mathdefault mtight">o</span><span class="mord mathdefault mtight">o</span><span class="mord mathdefault mtight">t</span><span class="mclose mtight">)</span></span></span></span></span></span></span></span></span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">−</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:0.64444em;vertical-align:0em;"></span><span class="mord">1</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel">=</span></span><span class="base"><span class="strut" style="height:0.5782em;vertical-align:-0.0391em;"></span><span class="mrel">&gt;</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:0.7719400000000001em;vertical-align:-0.13597em;"></span><span class="mord mathdefault">n</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel">≥</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:1.0213299999999998em;vertical-align:-0.08333em;"></span><span class="mord"><span class="mord">2</span><span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist" style="height:0.938em;"><span style="top:-3.113em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight"><span class="mord mathdefault mtight" style="margin-right:0.08125em;">H</span><span class="mopen mtight">(</span><span class="mord mathdefault mtight" style="margin-right:0.02778em;">r</span><span class="mord mathdefault mtight">o</span><span class="mord mathdefault mtight">o</span><span class="mord mathdefault mtight">t</span><span class="mclose mtight">)</span><span class="mbin mtight">÷</span><span class="mord mtight">2</span></span></span></span></span></span></span></span></span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">−</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:0.64444em;vertical-align:0em;"></span><span class="mord">1</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel">=</span></span><span class="base"><span class="strut" style="height:0.5782em;vertical-align:-0.0391em;"></span><span class="mrel">&gt;</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:0.66666em;vertical-align:-0.08333em;"></span><span class="mord mathdefault">n</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">+</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:0.78041em;vertical-align:-0.13597em;"></span><span class="mord">1</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel">≥</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:0.938em;vertical-align:0em;"></span><span class="mord"><span class="mord">2</span><span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist" style="height:0.938em;"><span style="top:-3.113em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight"><span class="mord mathdefault mtight" style="margin-right:0.08125em;">H</span><span class="mopen mtight">(</span><span class="mord mathdefault mtight" style="margin-right:0.02778em;">r</span><span class="mord mathdefault mtight">o</span><span class="mord mathdefault mtight">o</span><span class="mord mathdefault mtight">t</span><span class="mclose mtight">)</span><span class="mbin mtight">÷</span><span class="mord mtight">2</span></span></span></span></span></span></span></span></span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel">=</span></span><span class="base"><span class="strut" style="height:0.5782em;vertical-align:-0.0391em;"></span><span class="mrel">&gt;</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathdefault" style="margin-right:0.01968em;">l</span><span class="mord mathdefault">o</span><span class="mord"><span class="mord mathdefault" style="margin-right:0.03588em;">g</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.30110799999999993em;"><span style="top:-2.5500000000000003em;margin-left:-0.03588em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight">2</span></span></span></span><span class="vlist-s">​</span></span><span class="vlist-r"><span class="vlist" style="height:0.15em;"><span></span></span></span></span></span></span><span class="mopen">(</span><span class="mord mathdefault">n</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">+</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord">1</span><span class="mclose">)</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel">≥</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathdefault" style="margin-right:0.08125em;">H</span><span class="mopen">(</span><span class="mord mathdefault" style="margin-right:0.02778em;">r</span><span class="mord mathdefault">o</span><span class="mord mathdefault">o</span><span class="mord mathdefault">t</span><span class="mclose">)</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">÷</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:0.64444em;vertical-align:0em;"></span><span class="mord">2</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel">=</span></span><span class="base"><span class="strut" style="height:0.5782em;vertical-align:-0.0391em;"></span><span class="mrel">&gt;</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathdefault" style="margin-right:0.08125em;">H</span><span class="mopen">(</span><span class="mord mathdefault" style="margin-right:0.02778em;">r</span><span class="mord mathdefault">o</span><span class="mord mathdefault">o</span><span class="mord mathdefault">t</span><span class="mclose">)</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel">≤</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:0.64444em;vertical-align:0em;"></span><span class="mord">2</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">⋅</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathdefault" style="margin-right:0.01968em;">l</span><span class="mord mathdefault">o</span><span class="mord"><span class="mord mathdefault" style="margin-right:0.03588em;">g</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.30110799999999993em;"><span style="top:-2.5500000000000003em;margin-left:-0.03588em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight">2</span></span></span></span><span class="vlist-s">​</span></span><span class="vlist-r"><span class="vlist" style="height:0.15em;"><span></span></span></span></span></span></span><span class="mopen">(</span><span class="mord mathdefault">n</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">+</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord">1</span><span class="mclose">)</span></span></span></span></span></p>
<h3 id="与-avl-的比较"><a class="markdownIt-Anchor" href="#与-avl-的比较"></a> 与 avl 的比较</h3>
<p>两者都是经过优化的自平衡二叉树。有各自的自平衡算法，增删查效率都是log(n)但有一些区别。但从平衡性而言，AVL的平衡性更加严格，如下图所示情况。 红黑树允许较低的平衡性（但复杂度仍为log(n)）换取更少的自平衡操作。由于avl数平衡性高于红黑树，查询效率上会高于红黑树（但复杂度仍为log(n)）。红黑树算是比较「折衷」的平衡树方案，C++的STL中和JAVA的TreeMap&amp;HashMap都实现了红黑树以达到O(log(n)) 的插入删除的效果</p>
<style>
img {
margin:auto;
width:61.8%;
}
</style>

      
    </div>

    
    
    
      <footer class="post-footer">
        <div class="post-eof"></div>
      </footer>
  </article>
  
  
  

  </div>

  
  <nav class="pagination">
    <span class="page-number current">1</span><a class="page-number" href="/page/2/">2</a><a class="extend next" rel="next" href="/page/2/"><i class="fa fa-angle-right" aria-label="Next page"></i></a>
  </nav>



          </div>
          

        </div>
          
  
  <div class="toggle sidebar-toggle">
    <span class="toggle-line toggle-line-first"></span>
    <span class="toggle-line toggle-line-middle"></span>
    <span class="toggle-line toggle-line-last"></span>
  </div>

  <aside class="sidebar">
    <div class="sidebar-inner">

      <ul class="sidebar-nav motion-element">
        <li class="sidebar-nav-toc">
          Table of Contents
        </li>
        <li class="sidebar-nav-overview">
          Overview
        </li>
      </ul>

      <!--noindex-->
      <div class="post-toc-wrap sidebar-panel">
      </div>
      <!--/noindex-->

      <div class="site-overview-wrap sidebar-panel">
        <div class="site-author motion-element" itemprop="author" itemscope itemtype="http://schema.org/Person">
    <img class="site-author-image" itemprop="image" alt="Cyril Nee"
      src="https://blog-bucket-1300756499.cos.ap-chengdu.myqcloud.com/avatar.jpg">
  <p class="site-author-name" itemprop="name">Cyril Nee</p>
  <div class="site-description" itemprop="description">站在巨人的肩膀上。</div>
</div>
<div class="site-state-wrap motion-element">
  <nav class="site-state">
      <div class="site-state-item site-state-posts">
          <a href="/archives/">
        
          <span class="site-state-item-count">11</span>
          <span class="site-state-item-name">posts</span>
        </a>
      </div>
      <div class="site-state-item site-state-tags">
            <a href="/tags/">
          
        <span class="site-state-item-count">3</span>
        <span class="site-state-item-name">tags</span></a>
      </div>
  </nav>
</div>
  <div class="links-of-author motion-element">
      <span class="links-of-author-item">
        <a href="https://github.com/cyrilney" title="GitHub → https:&#x2F;&#x2F;github.com&#x2F;cyrilney" rel="noopener" target="_blank"><i class="fa fa-fw fa-github"></i>GitHub</a>
      </span>
      <span class="links-of-author-item">
        <a href="/mailto:/cyrilnee2513@gmail.com" title="E-Mail → mailto:&#x2F;&#x2F;cyrilnee2513@gmail.com" rel="noopener" target="_blank"><i class="fa fa-fw fa-envelope"></i>E-Mail</a>
      </span>
      <span class="links-of-author-item">
        <a href="https://instagram.com/cy.ril2513" title="Instagram → https:&#x2F;&#x2F;instagram.com&#x2F;cy.ril2513" rel="noopener" target="_blank"><i class="fa fa-fw fa-instagram"></i>Instagram</a>
      </span>
      <span class="links-of-author-item">
        <a href="https://leetcode-cn.com/u/cyril-3" title="Leetcode → https:&#x2F;&#x2F;leetcode-cn.com&#x2F;u&#x2F;cyril-3" rel="noopener" target="_blank"><i class="fa fa-fw fa-cubes"></i>Leetcode</a>
      </span>
  </div>



      </div>

    </div>
  </aside>
  <div id="sidebar-dimmer"></div>


      </div>
    </main>

    <footer class="footer">
      <div class="footer-inner">
        

<div class="copyright">
  
  &copy; 
  <span itemprop="copyrightYear">2020</span>
  <span class="with-love">
    <i class="fa fa-heart"></i>
  </span>
  <span class="author" itemprop="copyrightHolder">Cyril Nee</span>
</div>
  <div class="powered-by">Powered by <a href="https://hexo.io/" class="theme-link" rel="noopener" target="_blank">Hexo</a>
  </div>
  <span class="post-meta-divider">|</span>
  <div class="theme-info">Theme – <a href="https://pisces.theme-next.org/" class="theme-link" rel="noopener" target="_blank">NexT.Pisces</a>
  </div>

        
<div class="busuanzi-count">
  <script async src="/js/busuanzi.pure.mini.js"></script>
    <span class="post-meta-item" id="busuanzi_container_site_uv" style="display: none;">
      <span class="post-meta-item-icon">
        <i class="fa fa-user"></i>
      </span>
      <span class="site-uv" title="Total Visitors">
        <span id="busuanzi_value_site_uv"></span>
      </span>
    </span>
    <span class="post-meta-divider">|</span>
    <span class="post-meta-item" id="busuanzi_container_site_pv" style="display: none;">
      <span class="post-meta-item-icon">
        <i class="fa fa-eye"></i>
      </span>
      <span class="site-pv" title="Total Views">
        <span id="busuanzi_value_site_pv"></span>
      </span>
    </span>
</div>








        
      </div>
    </footer>
  </div>

  
  <script src="/lib/anime.min.js"></script>
  <script src="/lib/velocity/velocity.min.js"></script>
  <script src="/lib/velocity/velocity.ui.min.js"></script>
<script src="/js/utils.js"></script><script src="/js/motion.js"></script>
<script src="/js/schemes/pisces.js"></script>
<script src="/js/next-boot.js"></script>



  




  <script src="/js/local-search.js"></script>













  

  

  


<script>
NexT.utils.getScript('//unpkg.com/valine/dist/Valine.min.js', () => {
  var GUEST = ['nick', 'mail', 'link'];
  var guest = 'nick,mail,link';
  guest = guest.split(',').filter(item => {
    return GUEST.includes(item);
  });
  new Valine({
    el: '#comments',
    verify: false,
    notify: false,
    appId: 'I6PDwb2i2zmm5sosK0MSBIXj-gzGzoHsz',
    appKey: 'IjwGjHl0XISqFwV5zY11fyCI',
    placeholder: "every niceness reminds me of her.",
    avatar: 'mm',
    meta: guest,
    pageSize: '10' || 10,
    visitor: false,
    lang: 'zh-cn' || 'zh-cn',
    path: location.pathname,
    recordIP: false,
    serverURLs: ''
  });
}, window.Valine);
</script><!-- hexo-inject:begin --><!-- hexo-inject:end -->

</body>
</html>
